from typing import List

"""
121. 买卖股票的最佳时机
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

股票买卖系列题目
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 买卖股票的最佳时机含冷冻期
714. 买卖股票的最佳时机含手续费
"""


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        暴力
        """
        # maxResult = 0
        # for index in range(len(prices)-1):
        #     for i in range(len(prices)-1,index, -1):
        #         maxResult = max(prices[i] - prices[index], maxResult)
        #         # print(index, i)
        # return maxResult
        """
        一次遍历
        """
        minprice = int(1e9)
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit

    def maxProfit2(self, prices: List[int]) -> int:
        cost, profit = float('+inf'), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit



if __name__ == '__main__':
    s = Solution()
    print(s.maxProfit2([7, 1, 5, 3, 6, 4]))